﻿#ifndef __PRIORITYQUEUE__
#define __PRIORITYQUEUE__
#include "SortTool.h"
#define RECURSION 1
template <class item>
class priorityqueue{
public:
	priorityqueue(int n);
	~priorityqueue();
	bool empty() const;
	void insert(item value);
	item& getmax();
private:
	int curr_index;//下一个插入点
	int max_num;//队列的容量
	item * queue_handle;//队列的句柄
};

template <class item>
priorityqueue<item>::priorityqueue(int n):curr_index(0),max_num(n){
	queue_handle = new item[max_num];
	assert(queue_handle != NULL);
}

template <class item>
priorityqueue<item>::~priorityqueue(){
	delete [] queue_handle;
	queue_handle = NULL;
}

template <class item>
inline bool priorityqueue<item>::empty() const{
	return curr_index == 0;
}

#if RECURSION
template <class item>
void fixdown(item arr[], int index, int right){
	int l_child = index * 2 + 1,
		r_child = l_child + 1, largest;
	if(l_child <= right && arr[l_child] > arr[index]) largest = l_child;
	else largest = index;
	if(r_child <= right && arr[r_child] > arr[largest]) largest = r_child;
	if(largest != index){
		exchange(arr[index], arr[largest]);
		fixdown(arr, largest, right);
	}
}

template <class item>
void fixup(item arr[], int index){
	int father = (index - 1) / 2;
	if(index == 0 || arr[index] <= arr[father]) return;
	exchange(arr[index], arr[father]);
	fixup(arr, father);
}

#else
template <class item>
void fixdown(item arr[], int index, int right){
	for(;;){
		int l_child = index * 2 + 1, r_child = l_child + 1,	largest;
		if(l_child <= right && arr[l_child] > arr[index]) largest = l_child;
		else largest = index;
		if(r_child <= right && arr[r_child] > arr[largest])	largest = r_child;
		if(largest != index){
			exchange(arr[index], arr[largest]);	index = largest;
		}else break;	
	}
}

template <class item>
void fixup(item arr[], int index){
	for(;;){
		int father = (index - 1)/2;
		if(index == 0 || arr[index] <= arr[father]) break;
		exchange(arr[index], arr[father]);
		index = father;
	}
}
#endif

template <class item>
void priorityqueue<item>::insert(item value){
	if(curr_index >= max_num) return;
	queue_handle[curr_index++] = value;
	fixup(queue_handle, curr_index-1);
}

template <class item>
item& priorityqueue<item>::getmax(){
	int last = curr_index - 1;
	exchange(queue_handle[last], queue_handle[0]);//将最大值放到队尾
	fixdown(queue_handle, 0, last - 1);//保持队形
	return queue_handle[--curr_index];
}
#endif
